1. Field of the Invention
This invention relates to computer systems and, more particularly, to using data compression on data stored in dynamic random access memory in order to free space for storing performance-enhancing data.
2. Description of the Related Art
Memory often constitutes a significant amount of the cost of a computer system. However, the data stored within memory in a computer system is very compressible. Compressing data within memory is an attractive way of reducing memory cost since the effective size of a memory device can be increased if data compression is used. However, the complexities associated with managing compressed memory have limited the use of compression.
Data compression generally cannot compress different sets of data to a uniform size. For example, one page of data may be highly compressible (e.g., to less than 25% of its original size) while another page may only be slightly compressible (e.g., to 90% of its original size). As a result, one complexity that arises when managing memory that stores compressed data results from having to track sets of data that may each have variable lengths. In order to be able to access specific units of data in such a memory system, directory structures are used to track where each compressed unit of data is currently stored. However, these directory structures, which are typically stored in memory, add increased memory controller complexity, take up space in memory, and increase access times since an access to the directory is often necessary in order to be able to access the requested data.
Another potential problem with storing compressed data in memory arises because data may become less compressible over time. For example, if a cache line is compressed, there is a risk that a subsequent modification will change the data in that cache line such that it can no longer be compressed to fit within the space allocated to it, resulting in data overflow. This in turn may lead to incorrectness if there is no way to restore the data lost to the overflow. One proposed method of dealing with this problem involves both deallocating and reallocating space to a unit of data each time that data is modified. Implementing such a method increases memory controller complexity.
Another concern faced by system designers involves the increasing performance gap between memory and microprocessors. Microprocessor clock frequencies and issue rates (i.e., the rate at which instructions begin executing within the microprocessor) continue to improve more quickly than memory bandwidth is increasing. In terms of access latency (i.e., the time required for memory to respond to a memory access request), memory performance is also not increasing as rapidly as microprocessor capabilities. In some cases, memory latency is actually increasing with respect to microprocessor clock cycles. Accordingly, it is desirable to decrease the effective performance gap between memory and microprocessors.
One way in which the effects of the performance gap may be reduced is by prefetching data (e.g., application data and/or program code) from memory into a cache that has lower latency than the memory. The data may be prefetched while the microprocessor is operating on other data. The prefetch is typically initiated early enough so that the prefetched data is available in the cache just before the microprocessor is ready to begin operating on the prefetched data. So long as the processor is primarily operating on data that has already been prefetched into the cache, the processor will spend less time waiting for memory accesses to complete, despite the memory's slower access latency and lower bandwidth.
It is desirable to be able to use data compression and/or prefetching techniques in order to reduce the effective cost of memory and/or the effects of the performance gap between memory and microprocessors.